package com.hans.scala.sort

/**
 * 归并排序
 * Created by Hans on 2014/4/8.
 */
object MergeSort {
  def msort[T](less: (T, T) => Boolean)(xs: List[T]): List[T] = {

    def merge(xs: List[T], ys: List[T]): List[T] = (xs, ys) match {
      case (Nil, _) => ys
      case (_, Nil) => xs
      case (x :: xs1, y :: ys1) =>
        if (less(x, y)) x :: merge(xs1, ys)
        else y :: merge(xs, ys1)
    }

    val n = xs.length / 2
    if (n == 0) xs
    else {
      val (ys, zs) = xs splitAt n
      merge(msort(less)(ys), msort(less)(zs))
    }
  }

  def msort2[T](xs: List[T])(less: (T, T) => Boolean): List[T] = msort(less)(xs)

  def main(args: Array[String]) {
    msort((x: Int, y: Int) => x < y)(List(5, 1, 7, 3, 8))
    msort[Int](_ < _)(List(5, 1, 7, 3, 8)) //需要告诉其类型
    msort2(List(5, 1, 7, 3, 8))(_ < _) //可以根据第一个参数判断出类型
    msort[String]((x, y) => x < y)(List("5", "7", "1", "3", "8"))
  }
}
